// 回溯算法
// 骑士巡逻/N皇后/迷宫老鼠/数独

// 迷宫老鼠 - N*N矩阵，每个位置可能是空闲(1)或者被阻挡(0) 左上角的1是起点 右下角的1是终点
// 1 0 0 0
// 1 1 1 1
// 0 0 1 0
// 0 1 1 1
// 矩阵就是迷宫 老鼠的目标就是从 0，0 到 n-1， n-1 老鼠可以在水平或者垂直方向上任何未被阻挡(1)的位置上移动

export function ratInAMaze(maze) {
    const solution = [];
    for (let i = 0; i < maze.length; i++) {
        solution[i] = [];
        for (let j = 0; j < maze[i].length; j++) {
            solution[i][j] = 0;
        }
    }
    if (findPath(maze, 0, 0, solution) === true) {
        return solution
    }
    return 'NO PATH FOUND';
}

function findPath(maze, x, y, solution) {
    const n = maze.length;
    if (x === n-1 && y === n-1) {
        solution[x][y] = 1;
        return;
    }
    if (isSafe(maze, x, y) === true) {
        solution[x][y] = 1;
        if (findPath(maze, x+1, y, solution)) {
            return true;
        }
        if (findPath(maze, x, y+1, solution)) {
            return true;
        }

        solution[x][y] = 0;
        return false;
    }
    return false;
}

function isSafe(maze, x ,y) {
    const n = maze.length;
    if (x >= 0 && y >= 0 && x < n && y < n && maze[x][y] !== 0) {
        return true
    }
    return false;
}


// 数独
// 5 3 X X 7 X X X X
// 6 X X 1 9 5 X X X
// X 9 8 X X X X 6 X
// 8 X X X 6 X X X 3
// 4 X X 8 X 3 X X 1
// 7 X X X 2 X X X 6
// X 6 X X X X 2 8 X
// X X X 4 1 9 X X 5
// X X X X 8 X X 7 9

function  sudokuSolver(matrix) {
    if (solveSoduku(matrix) === true) {
        return matrix;
    }
    return '无解'
}

const UNASSIGNED = 0;

function solveSoduku(matrix) {
    let row = 0;
    let col = 0;

    let checkBlankSpaces = false;
    for (row = 0; row < matrix.length; row++) {
        for (col = 0; col < matrix.length; col++) {
            if (matrix[row][col] === UNASSIGNED) {
                checkBlankSpaces = true;
                break;
            }
        }
        if (checkBlankSpaces) {
            break;
        }
    }
    if (!checkBlankSpaces) {
        return true;
    }
    for (let num = 1; num <= 9; num++) {
        if (isSafe(matrix, row, col, num)) {
            matrix[row][col] = num;
            if (solveSoduku(matrix)) {
                return true;
            }
            matrix[row][col] = UNASSIGNED;
        }
    }
    return false;
}

function isSafe(matrix, row, col, num) {
    return (
        !usedInRow(matrix, row, num) &&
        !usedInCol(matrix, col, num) &&
        !usedInBox(matrix, row - (row % 3), col - (col % 3), num)
    )
}

function usedInRow(matrix, row, num) {
    for (let col = 0; col < matrix.length; col++) {
        if (matrix[row][col] === num) {
            return true;
        }
    }
    return false;
}

function usedInCol(matrix, col, num) {
    for (let row = 0; row < matrix.length; row++) {
        if (matrix[row][col] === num) {
            return true;
        }
    }
    return false;
}

function usedInBox(matrix, boxStartRow, boxStartCol, num) {
    for (let row = 0; row < 3; row++) {
        for (let col = 0; col < 3; col++) {
            if (matrix[row + boxStartRow][col + boxStartCol] === num) {
                return true
            }
        }
    }
    return false;
}

// 大O表示法/NP完全理论
// O(1) - 常数
function increment(num) {
    return ++num
}

// O(log(n))


//O((log(n))c)

// O(n) - n->输入数组的大小
function sequentialSearch(array, value, equalsFn = defaultEquals) {
    let cost = 0;
    for (let i = 0; i < array.length; i++) {
        cost++;
        if (equalsFn(value, array[i])) {
            return i
        }
    }
    console.log(`cost for sequentialSearch with input size ${array.length} is ${cost}`);
    return -1;
}

// array  = [1 , 2, 3, 4, 5, 6, 7, 8, 9 ,10]
// value = 1?

//O(n的2次方) n->输入参数大小
function bubbleSort(array, compareFn = defaultCompare) {
    const { length } = array;
    let cost = 0;
    for (i = 0; i < length; i++) {
        cost++;
        for (j = 0; j < length - 1; j++) {
            cost++
            if (compareFn(array[j], array[j + 1]) === Compare.BIGGER_THAN) {
                swap(array, j, j+1)
            }
        }
    }
    return array;
}


// O(n的c次方)

// O(c的n次方)

//     n     O(1)    O(log(n))   O(n)   O(nlog(n))  O(n的2次方) O(2的n次方)
//    10     1        1           10        10        100          1024
//    20     1        1.3         20        26.02      400        1048576
//    50     1        1.69        50        84.94      2500         inf
//   100     1        2           100       200        10000        inf
//   500     1        2.69        500       1349.48    250000       inf
//  1000     1        3           1000     3000        1000000      inf
//  10000    1        4           10000    40000       100000000    inf



